We call this the empty set or null set denoted by ∅
Singleton Set
: A set with one element
∅≡{∅} because thats a singleton set that contains the null set
Venn Diagrams
U
V. a. e. i. o. u
The universal set is denoted by ⋃ and is represented by the square of the venn diagram
The universal set contains all possible elements
The set V of all the vowels in the English alphabet can be written as:
V={a,e,i,o,u}
Subsets
Proper Subsets
Remember: ⟺ means iff replacing the statement if and only if
A⊂B⟺∀x(x∈A→x∈B)∧∃x(x∈B∧x∈/A)
Venn Diagram of a Proper Subset
Sets may have other sets as members
U
B
A
Sizes of Set
Let S be a set. If there are exactly n distinct elements in S where n is a nonnegative integer, we say that S is a finite set and that n is the cardinality of S. The cardinality of S is denoted by ∣S∣ where ∣S∣=n, we can thus determine that ∣∅∣=0
Principle of Inclusion - Exclusion
Let A and B be finite sets
Then ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣
think it terms of sets so we don't double count for the intersection elements
Given a set S, the power set of S is the set of all subsets of the set S
The Power set of S is denoted by P(S)
P(A)=\SetB∣B⊆A
Cartesian Products
The ordered n-tuple(a1,a2,...,an) is the ordered collection
We say that (a1,...,an)=(b1,...bn)iffa1=b1,a2=b2,...,an=bn or
∀(i=1,2,...n)(ai=bi)
Let A and B be sets. The Cartesian product of A and B, denoted A×B, is the set of all ordered pairs (a,b), where a∈A and b∈B
A×B=\Set(a,b)∣a∈A∧b∈B
The Cartesian product of the sets A1,A2,...An denoted by A1×A2×...×An is the set of ordered b-tuples (a1,a2,...,an) where ai belongs to Ai for i=1,2,...,n
Let A and B be sets. The union of these sets, denoted by A∪B, is the set that contain those elements that are either in AorB
A∪B=\Setx∣x∈A∨x∈B
Intersection of Sets
U
A
B
Let A and B be sets. The intersection of these sets, denoted by A∩B, is the set that contains those elements that are in AandB
A∩B=\Setx∣x∈A∧x∈B
Two sets called disjoint if there intersection is the empty set
In other words there is no overlap in the Venn Diagram
Difference of Sets
U
A
B
Let A and B be sets. The difference of these sets, denoted by A−B, is the set that contains those elements that are in Abut not in B
A−B=\Setx∣x∈A∧x∈/B
Difference between sets A and B is sometimes denoted by A∖B
Compliment of Sets
U
A
B
Let U be the universal set. The compliment of a set, denoted by Aˉ, is the set that contains those elements that are not in A thus U−A
Aˉ=\Setx∈U∣x∈/A
The compliment depends on what we mean by the universal set U
Set Identities
Equivalence
Name
A∩U=A A∪∅=A
Identity laws
A∪U=U A∩∅=∅
Domination laws
A∪A=A A∩A=A
Idempotent laws
Aˉˉ=AKind of like double negation right?
Complementation law
A∪B=B∪A A∩B=B∩A
Commutative laws
A∪(B∪C)=(A∪B)∪C A∩(B∩C)=(A∩B)∩C
Associative laws
A∪(B∩C)=(A∪B)∩(A∪C) A∩(B∪C)=(A∩B)∪(A∩C)
Distributive laws
A∩B=Aˉ∪B A∪B=Aˉ∩Bˉ
De Morgan's Laws
A∪(A∩B)=A A∩(A∪B)=A
Absorption laws
A∪Aˉ=U A∩Aˉ=∅
Complement laws
Proof of Demorgan's law for sets
Arbitrary Unions or Intersections
We can define arbitrary unions and intersections for a finite number of sets
A_1\cap A_2\cap\cdots\cap A_n&=\Set{x\mid x\in A_i\text{ for all }i=1,\cdots ,n}\\
A_1\cup A_2\cup\cdots\cup A_n&=\Set{x\mid x\in A_i\text{ for some }i=1,\cdots ,n}\\
Each subset of U can be represented as a bit string of length 10, where A⊆U is associated to the bit string Bit10(A)=(b1,b2,b3,b5,b4,b5,b6,b7,b8,b9,b10)
where bi=1ifi∈A and 0ifi∈/A
For each bit string of length 10 there is a subset of U and for each subset of U there is a bit string of length 10
We say there is a one-to-one corresponded between bitstrings of length 10 and the subsets of a set with 10 elements